package 左哥算法.ch15并查集;

import java.lang.reflect.InvocationTargetException;
import java.util.*;

/**
 * 并查集2.2版本，可以获取每个父节点的集合大小，以及获取集合个数.
 * 优化存储方式
 * 注意：使用此类需要重写T的hashCode与equals
 */
public class UnionFindSet<T> {
    /**
     * 存放父集合与子集和的映射
     */
    Map<T,T> map =new HashMap<>();
    /**
     * 存放每个集合的个数
     */
    Map<T,Integer> sizeMap=new HashMap<>();
    /**
     * 存放集合的根节点
     */
//    Set<T> set=new HashSet<>();

    public UnionFindSet() {

    }

    public UnionFindSet(Collection<T> collection) {
        for (T t : collection) {
            map.put(t,t);
            sizeMap.put(t,1);
        }
    }

    /**
     * 我需要在这个操作中完成什么？
     * 1.将小集合的父节点指向大集合。
     * 2.更新大集合的size。
     * 3.从set中移除小集合。
     */
    public void union(T a,T b){
        if (!map.containsKey(a)){
            init(a);
        }
        if (!map.containsKey(b)){
            init(b);
        }
        if (a.equals(b)){
            return;
        }
        T parentA = find(a);
        T parentB = find(b);
        if (parentA.equals(parentB)){
            return;
        }
        int sizeA=sizeMap.get(parentA);
        int sizeB =sizeMap.get(parentB);
        if (sizeB>sizeA){
            sizeMap.put(parentB,sizeA+sizeB);
            map.put(parentA,parentB);
            sizeMap.remove(parentA);
        }else {
            sizeMap.put(parentA,sizeA+sizeB);
            map.put(parentB,parentA);
            sizeMap.remove(parentB);
        }
    }
    public void init(T o){
        if (map.containsKey(o)){    //已经初始化过就退出
            return;
        }
        map.put(o,o);
        sizeMap.put(o,1);
//        set.add(o);
    }

    /**
     * 查找o的真正父节点，在这个过程中会使o及其所有父节点指向真正的父节点。
     */
    public T find(T o){
        T parent = map.get(o);
        if (parent==null||parent.equals(o)){
            return o;
        }
        parent=find(parent);
        map.put(o,parent);
        return parent;
    }

    /**
     * 返回target所在集合的大小
     */
    public int getSetSize(T target){
        Integer size = sizeMap.get(find(target));
        return size==null?0:size;
    }
    public int getSetCount(){
        return sizeMap.size();
    }
    public int getAllCount(){
        return map.size();
    }

    public boolean isSameSet(T o1,T o2){
        return find(o1).equals(find(o2));
    }

    public Map<T,Integer> getSizeMap(){
        return sizeMap;
    }
}
